TMSAT problem

Definition

$\mathtt{TMSAT} = \{\langle \alpha, x, 1^n, 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_\alpha \text{ outputs } 1 \text{ on input } \langle x, u \rangle \text{ within } t \text{ steps}\}$
where $M_\alpha$ denotes the (deterministic) TM represented by string $\alpha$.

Theorem

$\mathtt{TMSAT}$ is NP-complete.

Proof

Let $L$ be a NP language. Then $\exists p$ polynomial and verifier TM $M$ s.t. $x \in L$ iff $\exists u \{0,1\}^{p(\lvert x \rvert)}$ string satisfying $M(x,u) = 1$ and $M$ runs in time $q(n)$ for some polynomial $q$.

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 43.
2. https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf
3. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec04.pdf